package problem;

import javax.swing.tree.TreeNode;
import java.util.*;

/**
 * @author RunningShrimp
 * @date 2021/5/16  20:37
 * @see <a href="https://leetcode-cn.com/problems/binary-tree-preorder-traversal/">二叉树的前序遍历</a>
 */
public class BinaryTreePreorderTraversal {
    /**
     * 递归实现
     *
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> numList = new ArrayList<>();
        if (root == null) {
            return numList;
        }
        traversal(root, numList);
        return numList;
    }

    /**
     * 利用栈的特点
     *
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> numList = new ArrayList<>();
        if (root == null) {
            return numList;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            numList.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return numList;
    }


    /**
     * 以二叉树为中心，不断遍历左子树
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> numList = new ArrayList<>();
        if (root == null) {
            return numList;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while (node != null||!stack.isEmpty()){
            while (node!=null){
                numList.add(node.val);
                stack.push(node);
                node= node.left;

            }
            if(!stack.isEmpty()){
                node = stack.pop();
                node = node.right;
            }
        }
        return numList;
    }

    private void traversal(TreeNode node, List<Integer> numList) {
        if (node == null) {
            return;
        }
        numList.add(node.val);
        traversal(node.left, numList);
        traversal(node.right, numList);
    }

    private static class TreeNode {
        int val;
        TreeNode right;
        TreeNode left;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
